use std::collections::HashMap;
struct Solution {}

impl Solution {
  pub fn longest_dup_substring(s: String) -> String {
    let mut l: usize = 0;
    let mut r = s.len(); 
    fn judge(w: usize, t: &str) -> &str{
      let mut i = 0;
      let mut map: HashMap<&str, usize> = HashMap::new();
      while i + w <= t.len() {
        if let Some(n) = map.get_mut(&t[i..i + w]) {
          return &t[i..i + w];
        } else {
          map.insert(&t[i..i+w], 1);
        }
        i += 1;
      }
      ""
    }
    let mut ret = "";
    let mut m = (l + r) / 2;
    while l < m {
      let temp = judge(m, &s);
      // println!("{} {} {}", temp, ret , m);
      if temp == "" {
        r = m; 
      } else {
        ret = temp;
        l = m;
      }
      m = (l + r) / 2;
    } 
    ret.to_string()
  }
}

// 超时，因为检查重复字符串使用滑动窗口时间复杂度不满足要求